#include <stdio.h>
#include <stdlib.h>

#define FLAG -100

typedef int DataType;
typedef enum bool Bool;
enum bool {
    false, true
};

struct ListNode {
    DataType val;
    struct ListNode *next;
};
typedef struct ListNode *PNode;
typedef struct ListNode *LinkList;

Bool ListIsEmpty(LinkList L);
LinkList createLinkList_H();
void print_llist(LinkList L);
void sort(LinkList L);
void destroy_LinkList(LinkList L);

Bool ListIsEmpty(LinkList L)
{
    return L->next == NULL;
}

// 创建带头结点的链表
LinkList createLinkList_H()
{
    LinkList L;
    PNode p;
    L = (LinkList)malloc(sizeof(struct ListNode));
    L->next = NULL;
    int x;
    scanf("%d", &x);
    while (x != FLAG)
    {
        p = (PNode)malloc(sizeof(struct ListNode));
        p->val = x;
        p->next = L->next;
        L->next = p;
        scanf("%d", &x);
    }
    return L;
}

void print_llist(LinkList L)
{
    if (ListIsEmpty(L)) {
        printf("\n");
        return ;
    }
    PNode p;
    for (p = L->next; p != NULL; p = p->next)
    {
        printf("%d ", p->val);
    }
    printf("\n");
}

void sort(LinkList L) {
    if (ListIsEmpty(L)) {
        return ;
    }
	LinkList p,pre_L,q;
	p = L->next->next;		// 先保存下L的第二个元素，因为下一步要将L变成只有一个元素的有序表。  
	L->next->next = NULL;	// 将L变成只有一个元素的有序表
	// 从L的第二个元素开始遍历整个L直至表尾 
	while(p != NULL){
		q = p->next;
		pre_L = L;	// 先用pre_L来保存L,指向有序区域。
		while(pre_L->next !=NULL && pre_L->next->val < p->val) // 遍历pre_L所指向的有序表L，直至找到比p大的节点 
			pre_L = pre_L->next;
        // 插入该结点
		p->next = pre_L->next;
		pre_L->next = p;
        // 让p指向待排序区域里下一个结点
		p = q;
	} 
}

void destroy_LinkList(LinkList L)
{
    if (L == NULL) {
        return ;
    }
    PNode q;
    PNode tmp;
    q = L;
    while (q != NULL) {
        tmp = q->next;
        free(q);
        q = tmp;
    }
}

int main()
{
    LinkList L = createLinkList_H();
    print_llist(L);
    sort(L);
    print_llist(L);
    destroy_LinkList(L);
    return 0;
}
